//https://leetcode.cn/problems/binary-search/
package codeRandomThoughts.Test704二分查找;

public class Solution {
    public int search(int[] nums, int target) {
        //设置头尾两个指针
        int head = 0;
        int tail = nums.length - 1;

        //中间数的位置
        //int mid = (tail + head ) / 2;
        int mid = tail + (head - tail) / 2;//相比于上面的写法,这样的写法可以防止超过int的最大范围溢出
        //当找到想要的数或者查完数组后退出
        //没有找到target时,tail会小于head
        while (target != nums[mid]) {
            if (target < nums[mid]) {
                tail = mid - 1;
            } else if (target > nums[mid]) {
                head = mid + 1;
            }
            mid = tail + (head - tail) / 2;
            if (tail < head)
                return -1;
        }
        return mid;
    }
}
